//给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。 
//
// 岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。 
//
// 此外，你可以假设该网格的四条边均被水包围。 
//
// 
//
// 示例 1: 
//
// 输入:
//11110
//11010
//11000
//00000
//输出: 1
// 
//
// 示例 2: 
//
// 输入:
//11000
//11000
//00100
//00011
//输出: 3
//解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。
// 
// Related Topics 深度优先搜索 广度优先搜索 并查集


package leetcode.d_200_299;

//Java：岛屿数量
public class P200NumberOfIslands{
    public static void main(String[] args) {
        Solution solution = new P200NumberOfIslands().new Solution();
        char[][] grid = new char[][] {{'1','1','1','1','0'},{'1','1','0','1','0'},{'1','1','0','0','0'},{'0','0','0','0','0'}};
        solution.numIslands(grid);

        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    //这个解法有问题
    class Solution {
        int[] dx = new int[] {-1, 1, 0, 0};
        int[] dy = new int[] {0, 0, -1, 1};
        char[][] g;

        public int numIslands(char[][] grid) {
            int isIlands = 0;
            g = grid;
            for (int i = 0; i < g.length; i++) {
                for (int j = 0; j < g[i].length; j++) {
                    if (g[i][j] == '0'){
                        continue;
                    }
                    isIlands += sink(i, j);
                }
            }
            return isIlands;
        }

        private int sink(int i, int j) {
            if (g[i][j] == '0'){
                return 0;
            }

            g[i][j] = '0';

            for (int k = 0; k < dx.length; ++k) {
                int x = i + dx[k];
                int y = j + dy[k];
                if (x > 0 && x < g.length && y > 0 && y < g[i].length){
                    if (g[x][y] == '0'){
                        continue;
                    }
                    sink(x, y);
                }
            }

            return 1;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}